﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
using Emil.GMP;

namespace ProjectEulerSolutions.Problems
{
    /*
     * 

Consider the infinite polynomial series AF(x) = xF1 + x2F2 + x3F3 + ..., where Fk is the kth term in the Fibonacci sequence: 1, 1, 2, 3, 5, 8, ... ; that is, Fk = Fk−1 + Fk−2, F1 = 1 and F2 = 1.

For this problem we shall be interested in values of x for which AF(x) is a positive integer.
Surprisingly AF(1/2) 	 =  	(1/2).1 + (1/2)2.1 + (1/2)3.2 + (1/2)4.3 + (1/2)5.5 + ...
  	 =  	1/2 + 1/4 + 2/8 + 3/16 + 5/32 + ...
  	 =  	2

The corresponding values of x for the first five natural numbers are shown below.
x	AF(x)
√2−1	1
1/2	2
(√13−2)/3	3
(√89−5)/8	4
(√34−3)/5	5

We shall call AF(x) a golden nugget if x is rational, because they become increasingly rarer; for example, the 10th golden nugget is 74049690.

Find the 15th golden nugget.

     * */
    class Problem137 : IProblem
    {
        public string Calculate()
        {
            long n = 0;
            int count = 0;
            int target = 15;


            while (count < target)
            {
                n++;

                BigInt bigN = new BigInt(n.ToString());
                BigInt bigTemp = 5 * bigN * bigN + 2 * bigN + 1;

                if (bigTemp.IsPerfectSquare())
                {
                    count++;
                    Console.WriteLine("{0}: {1} - {2}", count, n, bigTemp);
                    if (count < target)
                    {
                        //preskočimo brojeve (jer je testiranje pokazalo da je svaki četvrti racionalan...
                        //iako bi mogo i sve to odjebat i samo računat fibonnacie ali kgj ionako je samo 13 ms
                        double phi = (Math.Sqrt(5) + 1) / 2;
                        double ratio = Math.Pow(phi, 4);
                        n = (long)(n * ratio);
                    }
                }
            }
            return n.ToString();
        }
    }
}

